Transversals in Linear Uniform Hypergraphs by Michael A. Henning & Anders Yeo

Author:Michael A. Henning & Anders Yeo
Language: eng
Format: epub
ISBN: 9783030465599
Publisher: Springer International Publishing

Since , either or and . ()

Claim M.3: If , then contains a double--component and .

Proof of Claim M.3: Suppose that . By Claim M.2, , and so . By Claim M.1, . Let e be the edge in . If e intersects only one of the copies of in X, then the other copy of is an -component in implying that , contradicting the fact that . Therefore, e intersects both copies of in X. By the linearity of H the edge e intersects each copy in one vertex, implying that contains a double--component. ()

Claim M.4: If , then contains an -component and .

Proof of Claim M.4: Suppose that , and let R be the special subhypergraph in X. By Claim M.1 we note that , and so R is a component of . Suppose, to the contrary, that . Among all degree-3 vertices, we choose the vertex x so that where j is a maximum; that is, X is chosen to contain a special subhypergraph of maximum possible size j. By supposition, , and so .

Suppose that each edge incident with x intersects R in at most two vertices. By Claim M.1, all three edges incident with x intersect R in at least one vertex, implying that in this case at least three neighbors of x in H belong to R. Since every special subhypergraph different from contains at most two vertices of degree 1, we can choose a neighbor y of x in R such that . Since every neighbor of x in R has degree at most 2 in R since H has maximum degree 3, this implies that , and so . This implies by Observation 8.1(p) that is connected or is disconnected with exactly two components, one of which consists of an isolated vertex. In both cases, since all three edges incident with x intersect R we note that either is connected and has cardinality at least or is disconnected with two components, one of which consists of an isolated vertex with the other component of cardinality at least . Analogously as with the vertex x, there is a special -set, Y, with satisfying or and .

If , then by our earlier observations, Y consists of a special subhypergraph of cardinality at least , contradicting the maximality of R. Hence, and . Analogously as with the vertex x (see Claim M.3), contains a double--component. Let and be the -pair of this double--component, and let be the linking edge that intersects them. We note that . By Observation 8.1(p), does not contain a double--component. Further, does not contain a component of order 4.

Suppose that the edge of belongs to R. If the edge does not belong to R, then is a component in (of order 4), a contradiction. Hence, the edge also belongs to R. If the edge in belongs to R, then would contain a double--component, a contradiction. Hence, the edge in does not belong to R and must therefore contain the vertex x.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.